/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package main;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * @author Pacific
 */
public class Resulter {
    private int[][] costMatrix ;
    private boolean[][] goMatrix ;
    private int homeCity ;
    private int normalizationCost = 0 ;
    
    static public int[][] copyArray( int [][] srcMatrix ) {
        int[][] destMatrix = new int[srcMatrix.length][] ;
        for( int i=0 ; i<srcMatrix.length ; ++i ) {
            destMatrix[i] = Arrays.copyOf(srcMatrix[i], srcMatrix.length) ;
        }
        return destMatrix ;
    }
    
    static public boolean[][] copyArray( boolean [][] srcMatrix ) {
        boolean[][] destMatrix = new boolean[srcMatrix.length][] ;
        for( int i=0 ; i<srcMatrix.length ; ++i ) {
            destMatrix[i] = Arrays.copyOf(srcMatrix[i], srcMatrix.length) ;
        }
        return destMatrix ;
    }
    
    public Resulter( int[][] costMatrix ) throws IOException {
        this.costMatrix = copyArray(costMatrix) ;
        goMatrix = new boolean[costMatrix.length][costMatrix.length] ;
        for( int i=0 ; i<goMatrix.length ; ++i ) {
            for( int j=0 ; j<goMatrix.length ; ++j )
                goMatrix[i][j] = false ;
        }
        homeCity = 0 ;
        
        buildMSTWithoutHome() ;
        connectHomeCity() ;
        connectHomeCity() ;
        normalize() ;
    }
    
    private Resulter( int[][] newCostMatrix, boolean[][] newGoMatrix, int newNormalizationCost ) {
        costMatrix = copyArray(newCostMatrix) ;
        goMatrix = copyArray(newGoMatrix) ;
        normalizationCost = newNormalizationCost ;
    }
    
    
    
    protected static String print( int[][] matrix) {
        StringBuilder builder = new StringBuilder() ;
        for( int i=0 ; i<matrix.length ; ++i ) {
            for( int j=0 ; j<matrix[i].length ; ++j ) {
                if( i == j || matrix[i][j]>Integer.MAX_VALUE-5000 )
                    builder.append((char)8734+" ") ;
                else
                    builder.append(matrix[i][j]+" ");
            }
            builder.append('\n');
        }
        return builder.toString() ;
    }
    
    public static String print( boolean[][] matrix ) {
        StringBuilder builder = new StringBuilder() ;
        for( boolean[] line : matrix ) {
            for( boolean value : line ) {
                builder.append(((value)?"1":"0")+" ");
            }
            builder.append('\n');
        }
        return builder.toString() ;
    }
    
    
    
    protected final void normalize() {
        normalizeLines() ;
        normalizeColumns() ;
    }
    
    protected boolean normalizeLines() {
        boolean normalizeSuccess = false ;
        for( int i=0 ; i<costMatrix.length ; ++ i ) {
            int min = Integer.MAX_VALUE ;
            for( int  j=0 ; j<costMatrix.length ; ++j ) {
                if( i == j )
                    continue ;
                min = (costMatrix[i][j]<min) ? costMatrix[i][j] : min ;
            }
            if( min != 0) {
                System.out.println("Increment COST of "+min);
                normalizationCost += min ;
                for( int  j=0 ; j<costMatrix.length ; ++j ) {
                    costMatrix[i][j] -= min ;
                }
                normalizeSuccess = true ;
            }
        }
        return normalizeSuccess ;
    }
    
    protected boolean normalizeColumns() {
        boolean normalizationSuccess = false ;
        for( int columnNum=0 ; columnNum<costMatrix.length ; ++columnNum ) {
            int min = Integer.MAX_VALUE ;
            for( int lineNum=0 ; lineNum<costMatrix.length ; ++lineNum ) {
                if( columnNum == lineNum)
                    continue ;
                int matrixValue = costMatrix[lineNum][columnNum] ;
                min = (matrixValue<min) ? matrixValue : min ;
            }
            if( 0 != min ) {
                System.out.println("Increment COST of "+min);
                normalizationCost += min ;
                for( int lineNum=0 ; lineNum<costMatrix.length ; ++lineNum ) {
                    costMatrix[lineNum][columnNum] -= min ;
                    normalizationSuccess = true ;
                }
            }
        }
        return normalizationSuccess ;
    }
    
    //!TODO invoke error when homeCity is last vertex
    protected final void buildMSTWithoutHome() throws IOException {
        final int SIZE = costMatrix.length -1 ;
        //Matrix for spanning tree
        boolean[][] spaningTree = new boolean[SIZE][SIZE] ;
        for( int i=0 ; i<SIZE ; ++i ) {
            for( int j=0 ; j<SIZE ; ++j )
                spaningTree[i][j] = false ;
        }
        //Matrix for visited marks
        boolean[] dotVisited = new boolean[SIZE] ;
        for( int i=0 ; i<SIZE ; ++i )
            dotVisited[i] = false ;        
        //Marks
        int[] dotsColors = new int[SIZE] ;
        int colorsCounter = 1 ;
        for( int i=0 ; i<SIZE ; ++i )
            dotsColors[i] = 0 ;
        //Build temp Matrix without home city
        int[][] tempMatrix = new int[SIZE][SIZE] ;
        for( int realMatrIterI=0, copyMatrIterI=-1  ; realMatrIterI<costMatrix.length ; ++realMatrIterI ) {
            ++copyMatrIterI ;
            if( realMatrIterI == homeCity )
                ++realMatrIterI ;
            for( int realMatrIterJ=0, copyMatrIterJ=-1 ; realMatrIterJ<costMatrix.length ; ++realMatrIterJ ) {
                ++copyMatrIterJ ;
                if( realMatrIterJ == homeCity )
                    ++realMatrIterJ ;
                tempMatrix[copyMatrIterI][copyMatrIterJ] = costMatrix[realMatrIterI][realMatrIterJ] ;
            }
        }
        
        System.out.println("Sub Matrix:\n"+print(tempMatrix));
        
        while( !colorsIsDifferant(dotsColors) ) {
            int x = -1 ;
            int y = -1 ;
            int min = Integer.MAX_VALUE ;
            
            //Find minimal element
            for( int i=0 ; i<tempMatrix.length ; ++i ) {
                for( int j=0 ; j<tempMatrix[i].length ; ++j ) {
                    if( i == j )
                        continue;
                    if( (tempMatrix[i][j] < min) && ((!dotVisited[i] || !dotVisited[j]) || dotsColors[i] != dotsColors[j]) ) {
                        min = tempMatrix[i][j] ;
                        x = i ;
                        y = j ;
                    }
                }
            }
            
            System.out.println("Add["+(x+1)+"]["+(y+1)+"]") ;
            //System.out.println("dotVisited["+(x+1)+"]="+dotVisited[x]+", dotVisited["+(y+1)+"]="+dotVisited[y]);
            //System.out.println("dotsColor["+(x+1)+"]="+dotsColors[x]+", dotsColor["+(y+1)+"]="+dotsColors[y]);
            
            //Mark dots            
            if( dotsColors[x] == 0 && dotsColors[y] == 0 ) {
                dotVisited[x] = true ;
                dotVisited[y] = true ;
                spaningTree[x][y] = true ;
                spaningTree[y][x] = true ;
                int color = colorsCounter++ ;
                dotsColors[x] = color ;
                dotsColors[y] = color ;
                //System.out.println("Finded dots with blank color");
            }
            else if( (dotsColors[x] != 0 && dotsColors[y] != 0) && (dotsColors[x] != dotsColors[y]) ) {
                spaningTree[x][y] = true ;
                spaningTree[y][x] = true ;
                int oldColor = dotsColors[y]>dotsColors[x] ? dotsColors[y] : dotsColors[x] ;
                int newColor = dotsColors[y]<dotsColors[x] ? dotsColors[y] : dotsColors[x] ;
                for( int i=0 ; i<dotsColors.length ; ++i ) 
                    if( dotsColors[i] == oldColor )
                        dotsColors[i] = newColor ;
                //System.out.println("Finded dots with differant color");
            } else if(dotsColors[x] == 0 || dotsColors[y] == 0) {
                dotVisited[x] = true ;
                dotVisited[y] = true ;
                spaningTree[x][y] = true ;
                spaningTree[y][x] = true ;
                int color = dotsColors[x] + dotsColors[y] ;
                dotsColors[x] = color ;
                dotsColors[y] = color ;
                //System.out.println("Find dots witch one hase blank color");
            } else {
                throw new Error("Unexpected Behavior") ;
                //Find dots with some color
            }
            
            
        }
        
        for( int realI=0, fictI=-1 ; realI<goMatrix.length ; ++realI ) {
            ++fictI ;
            if( realI == homeCity )
                ++realI ;
            for( int realJ=0, fictJ=-1 ; realJ<goMatrix.length ; ++realJ ) {
                ++fictJ ;
                if( realJ == homeCity )
                    ++realJ ;
                goMatrix[realI][realJ] = spaningTree[fictI][fictJ] ;
            }
        }
    }
    
    
    
    private boolean colorsIsDifferant( int[] array ) {
        for( int value : array )
            if (value != 1) {
                return false ;
            }
        return true ;
    }
    
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder() ;
        builder.append( print( costMatrix ) ) ;
        builder.append("ApproximateValue="+getTotalCost()); 
        builder.append('\n') ;
        builder.append( print( goMatrix ) ) ;
        return builder.toString() ;
    }

    private void connectHomeCity() {
        int indexOfMin = 0 ;
        int min = Integer.MAX_VALUE ;        
        for( int i=0 ; i<goMatrix.length ; ++i ) {
            if( i == homeCity )
                continue ;
            if( costMatrix[homeCity][i] < min && !goMatrix[homeCity][i] ) {
                min = costMatrix[homeCity][i] ;
                indexOfMin = i ;
            }
        }
        System.out.println("Connect Home city ["+homeCity+"]["+indexOfMin+"]");
        goMatrix[homeCity][indexOfMin] = true ;
        goMatrix[indexOfMin][homeCity] = true ;
    }

    public boolean isResult() {
        for(boolean[] line : goMatrix) {
            int counter = 0 ;
            for( boolean go : line ) {
                counter += (go)? 1 : 0 ;
            }
            if( counter != 2 )
                return false ;
        }
        return true ;
    }

    public int getTotalCost() {
        int sum = 0 ;
        for( int i=0 ; i<goMatrix.length ; ++i ) {
            for( int j=0 ; j<=i ; ++j ) {
                if( goMatrix[i][j] )
                    sum += costMatrix[i][j] ;
            }
        }
        sum /= 2 ;
        return sum + normalizationCost ;
    }

    private List<Resulter> getAssuptionForMoreIncidents() {
        List<Resulter> list = new ArrayList<>() ;
        int maxVertex = -1 ;
        int maxCounter = Integer.MIN_VALUE ;
        
        //find vertex with max incidents
        for( int i=0 ; i<goMatrix.length ; ++i ) {
            int counter = 0 ;
            for( int j=0 ; j<goMatrix[i].length ; ++j ) {
                if( goMatrix[i][j] )
                    counter++ ;
            }
            if( counter>maxCounter ) {
                maxCounter = counter ;
                maxVertex = i ;
            }
        }
        
        if( maxCounter > 2 ) {
            for( int j=0 ; j<goMatrix.length ; ++j ) {
                if( goMatrix[maxVertex][j] ) {
                    Resulter res = clone() ;
                    res.denieTrace(maxVertex, j) ;
                    if( !res.hasSmallCycle( maxVertex, j ) && !res.hasSmallCycle( j, maxVertex ) ) {
                        list.add(res);
                    }
                }
            }
            return list ;
        }
        return list ;
    }
    
    private List<Resulter> getAssuptionBetweenLessIncidents() {
        List<Resulter> list = new ArrayList<>() ;
        int vert1 = 0 ;
        //find vertex with incidents less 2
        for( int i=0 ; i<goMatrix.length ; ++i ) {
            int counter = 0 ;
            for( int j=0 ; j<goMatrix.length ; ++j ) {
                if( goMatrix[i][j] )
                    counter++ ;
            }
            if( counter < 2 ) {
                vert1 = i ;
                break ;
            }
        }
        
        Resulter newRes = null;
        int vert2 = -1 ;
        int i =vert1 ;
        do {
            i++ ;
            for( ; i<goMatrix.length ; ++i ) {
                if( vert1 == i )
                    continue;
                int counter = 0 ;
                for( int j=0 ; j<goMatrix.length ; ++j ) {
                    if( goMatrix[i][j] )
                        counter++ ;
                }
                if( counter < 2 && !goMatrix[vert1][i]) {
                    vert2 = i ;
                    break ;
                }
            }

            newRes = clone() ;
            newRes.goTrace( vert1, vert2 ) ;

        } while ( newRes.hasSmallCycle(vert1, vert2) ) ;
        list.add( newRes ) ;
        
        return list ;
    }
    
    
    
    
    public List<Resulter> getAssumptions() throws IOException {
        List<Resulter> list = new ArrayList<>() ;
        
        list.addAll( getAssuptionForMoreIncidents() ) ;
        if( list.size() > 0 )
            return list ;
        
        
        
        list.addAll( getAssuptionBetweenLessIncidents() ) ;
        
        return list ;
    }
    
    protected void denieTrace( int x, int y ) {
        System.out.println("DenieTrace "+x+"-"+y);
        costMatrix[x][y] = Integer.MAX_VALUE ;
        costMatrix[y][x] = Integer.MAX_VALUE ;
        goMatrix[x][y] = false ;
        goMatrix[y][x] = false ;
        normalize() ;
    }
    
    protected void goTrace( int x, int y ) {
        System.out.println("GoTrace "+x+"-"+y);
        goMatrix[x][y] = true ;
        goMatrix[y][x] = true ;
    }
    
    @Override
    public Resulter clone() {
        Resulter newR = new Resulter( costMatrix, goMatrix, normalizationCost ) ;
        return newR ;
    }
    
    public boolean[][] getGoMatrix() {
        return goMatrix ;
    }
    
    private boolean hasSmallCycle(int x, int y) {
        int currX = x ;
        int currY = y ;
        int counter = 0 ;
        do {
            int incedentsCounter = 0 ;
            int nextVertexNum = currY ;
            for( int i=0 ; i<goMatrix.length ; ++i ) {
                if( goMatrix[currX][i] ) {
                    incedentsCounter++ ;
                    if( i != currY )
                        nextVertexNum = i ;
                }
            }
            if( incedentsCounter != 2 )
                return false ;
            int temp = currX ;
            currX = nextVertexNum ;
            currY = temp ;
            counter++ ;
        } while( currX != x && currY != y ) ;
        if( counter == goMatrix.length )
            return false ;
        else
            return true ;
    }
}
